//
// Created by deng on 18-11-28.
//

#include "negamax.h"
#include <iostream>
#include "solution.h"

namespace doudizhu_endgame {

    Negamax::Negamax() = default;

    Negamax::~Negamax() {
        destroy_tree(tree_);
    }

/**
 * 计算下一层节点
 * @param node
 */
    void Negamax::gen_nodes(TreeNode *node) {
        if (node->turn == 1) { //农民出牌
            std::vector<Pattern *> selections;
            //此处将出牌的可能都放到selections
            doudizhu_.next_hand(node->farmer, node->last_move, selections);
            //扩容
            node->child.reserve(selections.size());
            //遍历可能出牌的牌组
            for (Pattern *move: selections) {
                CardSet after_play;
                //打出牌组move,剩下的手牌after_play=node->farmer
                doudizhu_.play(node->farmer, move, after_play);
                //每一次出牌就是一个节点,move就是对方出的牌
                auto child = new TreeNode{0, 0, node->lord, after_play, move};
                //农民赢了,做剪枝，某一个牌组能直接出完
                if (after_play.empty()) {
                    child->score = -1;
                    //释放剩余空节点
                    for (TreeNode *i: node->child) {
                        delete i;
                    }
                    std::vector<TreeNode *>().swap(node->child);
                    node->child.emplace_back(child);
                    return;
                }
                node->child.emplace_back(child);
            }

        } else {//该地主出牌
            std::vector<Pattern *> selections;
            doudizhu_.next_hand(node->lord, node->last_move, selections);
            //申请空间
            node->child.reserve(selections.size());
            //遍历能出的牌组，构建下一层节点
            for (Pattern *move: selections) {
                CardSet after_play;

                //打出牌组move后，node->lord= after_play更新:去掉move中的牌
                doudizhu_.play(node->lord, move, after_play);
                //构建子节点，也就是农民轮次的状态节点:
                //轮次:农民
                //地主手牌: after_play
                //农民手牌：不变
                //move就是对手(地主)打出的牌

                auto child = new TreeNode{1, 0, after_play, node->farmer, move};
                //如果地主手牌全部打完，表示地主赢了，那对农民child而言，分数=-1为输。
                if (after_play.empty()) {
                    child->score = -1;//地主赢，农民输child分数=-1
                    //删除无用空节点
                    for (TreeNode *i: node->child) {
                        delete i;
                    }
                    std::vector<TreeNode *>().swap(node->child);
                    //走到决胜的节点了，已经有赢的方案了，后续的兄弟节点就不需要遍历了
                    node->child.emplace_back(child);
                    return;
                }
                //挂载子节点
                node->child.emplace_back(child);
            }
        }
    }

    /**
     * bfs打印搜索树，这是为了方便看到每一轮做出那些决策
     * @param node
     * @param queue 引入队列做bfs
     */
    void Negamax::dumpSearch(TreeNode *root, deque<TreeNode *> &queue) {
        if (root == NULL) {
            return;
        }
        queue.push_back(root);
        TreeNode *p_root = root;
        cout << "--------------打印搜索树start----------------" << "\n";
        while (!queue.empty()) {
            //先加子节点
            for (TreeNode *&child: p_root->child) {
                queue.push_back(child);
            }

            TreeNode *node = queue.front();
            cout << BOLDGREEN << "出: [" << node->last_move->hand.str() << "]" << RESET << "\n";
            cout << "currt loard hand: [" << node->lord.str() << "]\n";
            cout << "currt farmer hand:[" << node->farmer.str() << "]\n";
            cout << "currt turn:[" << (int) (node->turn) << "]\n";
            cout << "currt score:[" << (int) (node->score) << "]\n";
            //弹出节点
            queue.pop_front();
            p_root = queue.front();
        }
        cout << "--------------打印搜索树end----------------" << "\n";
    }

    int8_t Negamax::negamax(TreeNode *node) {
        nodes_searched_ += 1;
        int8_t search = table_.get(node);
        //缓存命中，直接返回分值
        if (search != 0) {
            hash_hit_ += 1;
            return search;
        }
        //开始构建出牌的选择分支
        gen_nodes(node);
        int8_t score = -1;
        //开始dfs
        for (TreeNode *&child: node->child) {
            int8_t val{};
            //basecase
            if (child->score != 0) {//+-1表示出牌方案child已经决出胜负
                val = -child->score;
                nodes_searched_ += 1;
            } else {
                //dfs
                val = -negamax(child);
            }
            //如果有让自己赢的情况，则不需要遍历其他出牌策略了,更新分数为赢
            if (val > 0) {
                score = val;
                break;          //发生剪枝
            }
        }

        node->score = score;
        table_.add(node);
        //剪枝，删掉农民赢的节点
        pruning_tree(node);

        return score;
    }

/**
 * 开始对称博弈,构建搜索树
 * @param lord
 * @param farmer
 * @return
 */
    TreeNode *Negamax::search(const CardSet &lord, const CardSet &farmer) {
        CardSet pass;
        Pattern start = {-1, Pass, pass};
        //根节点，地主先出
        auto root = new TreeNode{0, 0, lord, farmer, &start};
        //开始dfs
        negamax(root);
        tree_ = root;
        deque<TreeNode *> q;
        dumpSearch(tree_, q);

        return root;
    }

    TreeNode *Negamax::search(const CardSet &lord, const CardSet &farmer, Pattern *last) {
        auto root = new TreeNode{0, 0, lord, farmer, last};
//    std::cout << "--------------构建搜索树restart----------------" << "\n";
//    std::cout << BOLDGREEN << "出: [" << root->last_move->hand.str() << "]" << RESET << "\n";
//    std::cout << "currt loard hand: [" << root->lord.str() << "]\n";
//    std::cout << "currt farmer hand:[" << root->farmer.str() << "]\n";
        negamax(root);
        tree_ = root;

        return root;
    }


/**
 * 减掉让地主输的节点
 * @param node
 */
    void Negamax::pruning_tree(TreeNode *node) {
        if (node->turn == 0) {//删掉让地主输的节点,站在地主的立场，child.back()->score=1表示农民赢,不允许，剪枝!
            //删除掉地主不能赢的节点
            while (!node->child.empty() && node->child.back()->score != -1) { // 删掉农民赢的节点
                destroy_tree(node->child.back());
                node->child.pop_back();
            }
            //todo 这块没怎么看明白:删除掉不可能的节点，剩下的都是合法节点，幺麽输幺麽赢
            if (!node->child.empty()) {
                //todo 这个交换是啥意思？
                std::swap(node->child.front(), node->child.back());
                //然后
                while (node->child.size() > 1) {
                    destroy_tree(node->child.back());
                    node->child.pop_back();
                }

            } else {
                //no child's score is -1
            }

        } else {
            //not pruning
        }
    }

    void Negamax::destroy_tree(TreeNode *node) {
        if (!node->child.empty()) {
            for (TreeNode *i: node->child) {
                destroy_tree(i);
            }
            std::vector<TreeNode *>().swap(node->child);
        }

        delete node;
    }

    void TranspositionTable::add(TreeNode *node) {
        uint64_t key = gen_key(node);
        auto it = table_.find(key);

        if (it == table_.end()) {
            this->table_.emplace(key, node->score);

        } else {
            //not add
        }
    }

    size_t TranspositionTable::size() {
        return table_.size();
    }

    int8_t TranspositionTable::get(TreeNode *node) {
        uint64_t key = gen_key(node);
        auto it = table_.find(key);

        if (it == table_.end()) {
            return 0;

        } else {
            return it->second;
        }
    }

    uint64_t TranspositionTable::gen_key(TreeNode *node) {
        uint64_t val = 0;

        val ^= node->farmer.to_ullong() + 0x9e3779b9 + (val << 6) + (val >> 2);
        val ^= node->lord.to_ullong() + 0x9e3779b9 + (val << 6) + (val >> 2);
        val ^= node->last_move->hand.to_ullong() + 0x9e3779b9 + (val << 6) + (val >> 2);
        val ^= node->turn + 0x9e3779b9 + (val << 6) + (val >> 2);

        return val;
    }

}//namespace doudizhu_endgame
